﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace FrogEngine
{
	public class GameEntityOctree<T> where T : I3DGameEntity
	{
		public class GameEntityOctreeNode<K> where K : I3DGameEntity
		{
			public GameEntityOctreeNode(Voxel box, int depth)
			{
				this.Box = box;
			}

			public Voxel Box { get; set; }
			public K Content { get; set; }
			public int Depth { get; private set; }
			public IList<GameEntityOctreeNode<K>> Children { get; private set; }
		}

		public GameEntityOctree(IEnumerable<T> entities)
		{
			// flatten primitives into a point cloud
			HashSet<Vector3> vertices = new HashSet<Vector3>();
			foreach (var entity in entities)
				vertices.Add(entity.Position);

			this.AABB = BoundingBox.CreateFromPoints(vertices);
			var voxel = new Voxel(null, this.AABB.Min, this.AABB.Max);
			this.Root = new GameEntityOctreeNode<T>(voxel, 0);

			foreach (var e in entities)
				this.InsertItem(e);
		}

		public BoundingBox AABB { get; private set; }
		private GameEntityOctreeNode<T> Root { get; set; }
		public int Height { get; private set; }

		public IEnumerable<Voxel> this[int index]
		{
			get 
			{
				if (index < 0 || index > this.Height)
					return null;
				if (index == 0)
					return new List<Voxel> { this.Root.Box };
				
				List<Voxel> retVal = new List<Voxel>();
				Queue<GameEntityOctreeNode<T>> bfsQueue = new Queue<GameEntityOctreeNode<T>>();
				bfsQueue.Enqueue(this.Root);
				while (bfsQueue.Count != 0)
				{
					var node = bfsQueue.Dequeue();
					if (node.Depth == index)
						retVal.Add(node.Box);
					else if (node.Depth < index)
						foreach (var c in node.Children)
							bfsQueue.Enqueue(c);
				}

				return retVal;
			}
		}

		public void InsertItem(T item)
		{
			insert(this.Root, item, 0);
		}

		private void insert(GameEntityOctreeNode<T> node, T item, int depth)
		{
			// 3 Cases: Content == null and Children count == 0, Content != null and Children count == 0, and Content == null && Children count != 0
			// no other cases should occur
			if (node.Content == null && node.Children.Count == 0)
			{
				// if there's no content and no children, then this is a leaf and the item can stay here
				node.Content = item;
				if (depth > this.Height)
					this.Height = depth;
			}
			else if (node.Content != null && node.Children.Count == 0)
			{
				// if there is content and no children, then this is a leaf that needs to be subdivided
				// to accomodate the new item... bubble the content of node down to the appropriate
				// child, then figure out which child node the item should go to and recursively call insert
				var boxes = node.Box.Subdivide();
				GameEntityOctreeNode<T> nodeToInsertAt = null;
				foreach (Voxel v in boxes)
				{
					var oNode = new GameEntityOctreeNode<T>(v, node.Depth + 1);
					if (node.Content != null && v.IsInside(node.Content.Position))
					{
						oNode.Content = node.Content;
						node.Content = default(T);
					}

					if (v.IsInside(item.Position))
						nodeToInsertAt = oNode;

					node.Children.Add(oNode);
				}

				insert(nodeToInsertAt, item, ++depth);
			}
			else if (node.Content == null && node.Children.Count != 0)
			{
				GameEntityOctreeNode<T> nodeToInsertAt = null;
				foreach (var oNode in node.Children)
				{
					if (oNode.Box.IsInside(item.Position))
					{
						nodeToInsertAt = oNode;
						break;
					}
				}

				if (nodeToInsertAt != null)
					insert(nodeToInsertAt, item, ++depth);
			}
		}
	}
}
